The evolution of computing devices such as computers, mobile phones, game consoles, personal digital assistants, etc., and the limitations of centralized networks have made the concept of a distributed network more attractive. Such a distributed network is called today a peer-to-peer network, or P2P network.
A P2P network includes any distributed network architecture composed of participants that make a portion of their resources (for example, processing power, storage capability or network bandwidth) available to other network participants, without the need for central coordination instances, e.g., servers. The participants in the P2P network, the peers, may be both suppliers and consumers of resources. This is in contrast to the traditional client-server model in which only the server supplies the resources and the clients consume them.
P2P networks often implement an Application Layer overlay network on top of the native or physical network topology. Such overlays are used for indexing and peer discovery. Content is typically exchanged directly over the underlying Internet Protocol (IP) network. P2P networks may be divided into structured networks and unstructured networks.
In structured P2P networks, connections in the overlay are fixed. These networks typically use distributed hash table-based (DHT) indexing, such as in the Chord system, which was described by Stoica et al. in “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” Proceedings of the ACM SIGCOMM '01 Conference, August 2001, the entire content of which is incorporated here by reference.
Structured P2P networks employ a globally consistent protocol to ensure that any node can efficiently route a search to some peer that has the desired file. Such a guarantee necessitates a more structured pattern of overlay links. The most common type of structured P2P network is the DHT, in which a variant of consistent hashing is used to assign ownership of each file to a particular peer, in a way analogous to a traditional hash table's assignment of each key to a particular array slot.
Unstructured P2P networks do not provide any algorithm for organization or optimization of network connections.
Structured P2P networks based on DHTs can be enhanced by using load balancing mechanisms. In the context of this application, the term load is understood to mean an amount of network traffic a peer has to forward to other peers. It is believed that efficient load balancing mechanisms are a requirement for P2P networks that are targeted for large-scale deployments.
Current load balancing mechanisms are either trying to achieve an even distribution of objects (e.g., content) among peers, make the address space (as the peers are entering and leaving the network continuously, the address space changes in time and may become unevenly populated) as evenly populated as possible, or both.
However, the current load balancing mechanisms are limited in their efficiency as shown by FIG. 1. FIG. 1 shows how imbalanced the load is in an unmodified Bamboo network (see Rhea et al., Handling Churn in a DHT, UC Berkeley technical report, CSD-03-1299, December 2003, the entire content of which is incorporated herein by reference). A similar situation is present in a Chord network. The data shown in FIG. 1 is measured based on a real Bamboo implementation. It can be seen from the figure that there are 3491 peers in the network that have forwarded less than 100 messages, and that there are 198 peers that have forwarded more than 3000 messages (the average is 218 messages). If the load would have been evenly distributed, each peer would have forwarded approximately 218 messages. Not visible in the figure, the least loaded peer did not forward any message and the most loaded peer forwarded 34,819 messages. Thus, FIG. 1 indicates that existing balancing methods are not able to cope with the realities in the P2P network.
Next, problems associated with existing load balancing mechanisms are briefly discussed. Many load balancing mechanisms are using the concept of virtual servers. Virtual servers are a technique in which a single physical peer is mapped to multiple virtual peers and each virtual peer has an unrelated peer-id. The problems associated with this technique based on virtual servers are that this technique requires more connections to other peers than the DHTs without virtual servers. This makes the mobile peers to have their battery drained quicker and is unsuitable for middlebox traversal. Also, this concept requires that one physical peer has multiple peer-ids, which makes hard the task of assigning cryptographic peer-ids for peers.
Other load balancing mechanisms are attempting to minimize the variation between partition sizes. In other words, these mechanisms try to create a situation where peers have equally sized partitions. When a new peer joins the network, these mechanisms try to find, by using probes, a relatively large partition in the P2P network, split it, and place the new peer into that partition to reduce the large partition. In addition, some mechanisms also balance partitions when a peer leaves from the P2P network by, for example, changing a peer-id of a peer in the P2P network. One problem with these mechanisms is that peers have to accept arbitrary peer-ids and thus, it is hard to assign cryptographic peer-ids for peers.
One existing load balancing mechanism is using the power of two choices paradigm. The load balancing in this case is focused on creating an even distribution of objects in the P2P network despite the differences in partition sizes. The load balancing works in a manner in which objects are stored to the less loaded of two, or more, peers in the P2P network. A problem with this approach is that it balances only the load related to storing an object, and not the load related to forwarding the network traffic, i.e., some peers are still overloaded in terms of traffic.
To summarize, all of the current solutions have one or more of the following undesirable features: require relatively large number of fingers per peer (which drains battery and is unsuitable for middlebox traversal), require one physical peer to have multiple peer-ids or require peers to accept arbitrary peer-ids (which makes hard to assign cryptographic peer-ids for peers), or balance only the object distribution (i.e., some peers are still overloaded with network traffic).
Accordingly, it would be desirable to provide devices, systems and methods that avoid the afore-described problems and drawbacks.